package com.lsa.the6046j.l5;

import java.util.ArrayList;
import java.util.List;

import com.lsa.helpers.Pair;
import com.lsa.helpers.Utils;
import com.lsa.shenn.common.AbstractSorter;

public class CountingSort extends AbstractSorter{
	List<Integer> sort(List<Integer> l, int min, int max) {
		List<Integer> result = new ArrayList<>();
		result.addAll(l);
		
		int[] freq = new int[max - min + 1];
		for (int i = 0; i < l.size(); i++) {
			freq[l.get(i) - min]++;
		}
		
		for (int i = 1; i < freq.length; i++) {
			freq[i] += freq[i-1];
		}
		
		for (int i = l.size()-1; i > -1 ; --i) {
			result.set(freq[l.get(i) - min]-1, l.get(i));
			freq[l.get(i) - min]--;
		}
		
		return result;
	}

	@Override
	public List<Integer> sort(List<Integer> l) {
		if (l.isEmpty()) {
			return l;
		}
		Pair<Integer, Integer> minMax = Utils.minMax(l);
		return sort(l, minMax.getFirst(), minMax.getSecond());
	}
}
